package summary;


import java.util.HashMap;
import java.util.Map;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/4 21:46
 * LRU 缓存
 */
public class Title146 {

    /**
     * 双向链表中的节点
     */
    class Node{
        private int key;

        private int val;

        private Node pre;

        private Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    class DoubleList {
        private int size;

        private Node head;

        private Node tail;

        public DoubleList() {
            //初始化双向链表
            head = new Node(0, 0);
            tail = new Node(0, 0);
            head.next = tail;
            tail.pre = head;
            size = 0;
        }

        /**
         * 在链表尾部添加元素
         * @param x
         */
        public void addLast(Node x) {
            x.pre = tail.pre;
            x.next = tail;
            tail.pre.next = x;
            tail.pre = x;
            size++;
        }

        /**
         * 删除链表中的某个元素
         * @param x
         */
        public void remove(Node x) {
            x.pre.next = x.next;
            x.next.pre = x.pre;
            size--;
        }

        /**
         * 删除链表第一个元素,并返回该节点
         */
        public Node removeFirst() {
            if (head.next == tail) {
                return null;
            }
            Node first = head.next;
            remove(first);
            return first;
        }

        /**
         * 返回列表长度
         * @return
         */
        public int size(){
            return size;
        }
    }

    /**
     * 创建hash表 <key,Node>
     */
    private Map<Integer, Node> hash;

    /**
     * 创建双向链表
     */
    private DoubleList cache;

    /**
     * 创建链表最大容量
     */
    private int max_capacity;

    public Title146(int capacity) {
        this.max_capacity = capacity;
        hash = new HashMap<>();
        cache = new DoubleList();
    }

    public int get(int key) {
        if (!hash.containsKey(key)) {
            return -1;
        }
        //包括这个key，更新双向链表的位置
        Node x = hash.get(key);
        cache.remove(x);
        cache.addLast(x);
        return x.val;
    }


    public void put(int key, int value) {
        if (hash.containsKey(key)) {
            //更新值
            Node x = hash.get(key);
            cache.remove(x);
            cache.addLast(x);
            x.val = value;
            hash.put(key, x);
        }else{
            //创建一个新的key，value 放在链表的队尾
            Node x = new Node(key, value);
            cache.addLast(x);
            hash.put(key, x);
            if (max_capacity > cache.size()) {
                //删除链表头
                Node node = cache.removeFirst();
                hash.remove(node.key);
            }
        }
    }

//    /**
//     * 将某个key提升为最近使用  get
//     * @param key
//     */
//    private void makeKeyRecently(int key) {
//        Node x = hash.get(key);
//        cache.remove(x);
//        cache.addLast(x);
//    }

//    /**
//     * 添加最近使用的元素  key value
//     * @param key
//     * @param value
//     */
//    private void addRecently(int key, int value) {
//        Node x = new Node(key, value);
//        cache.addLast(x);
//        hash.put(key, x);
//    }
//
//    /**
//     * 删除某个key
//     * @param key
//     */
//    private void removeKey(int key) {
//        Node x = hash.get(key);
//        cache.remove(x);
//        hash.remove(key);
//    }
//
//    /**
//     * 删除最久未使用
//     */
//    private void removeLeastRecentlyUse() {
//        Node node = cache.removeFirst();
//        hash.remove(node.key);
//    }
//
//    public int get(int key) {
//        if (!hash.containsKey(key)) {
//            return -1;
//        }
//        makeKeyRecently(key);
//        return hash.get(key).val;
//    }
//
//    public void put(int key, int value) {
//        if (hash.containsKey(key)) {
//            removeKey(key);
//            addRecently(key, value);
//            return;
//        }
//        addRecently(key, value);
//        if (cache.size() > max_capacity) {
//            //弹出最久未使用
//            removeLeastRecentlyUse();
//        }
//    }

    public static void main(String[] args) {

    }
}
